import java.util.ArrayList;
import java.util.List;

/**
 * 78. 子集
 */
public class Solution_78 {
    List<Integer> temp = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();

    /**
     * 递归回溯
     * <p>
     * 时间复杂度：O(n*2^n)。一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。
     * <p>
     * 空间复杂度：O(n)。临时数组 temp 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。
     */
    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(temp));
            return;
        }
        temp.add(nums[cur]);
        dfs(cur + 1, nums);
        // 回溯
        temp.remove(temp.size() - 1);
        dfs(cur + 1, nums);
    }

    public static void main(String[] args) {
        Solution_78 solution = new Solution_78();
        int[] nums = { 1, 2, 3 };
        List<List<Integer>> ans = solution.subsets(nums);
        System.out.println(ans);
    }
}
